home *** CD-ROM | disk | FTP | other *** search
/ The PC-SIG Library 10 / The PC-Sig Library - Shareware for the IBM PC and Compatibles (PC-SIG)(Tenth Edition Disks 1-2804)(1991).iso / PC_SIGCD / 22 / 4 / DISK2247.ZIP / CBASE101.ZIP / BTREE101.ZIP / KYOPS.C < prev    next >
Text File  |  1990-06-20  |  14KB  |  518 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)kyops.c    1.4 - 90/06/20" */
  5.  
  6. #include <blkio.h>
  7. #include <errno.h>
  8. /*#include <stddef.h>*/
  9. /*#include <string.h>*/
  10.  
  11. /* local headers */
  12. #include "btree_.h"
  13.  
  14. /*man---------------------------------------------------------------------------
  15. NAME
  16.      bt_kychildp - btree node child
  17.  
  18. SYNOPSIS
  19.      #include "btree_.h"
  20.  
  21.      bpos_t *bt_kychildp(btnp, kn)
  22.      btnode_t *btnp;
  23.      int kn;
  24.  
  25. DESCRIPTION
  26.      bt_kychildp returns a pointer to the knth child in node btnp.
  27.      If btnp is not a valid btree node or if kn < 0 or
  28.      kn > btnp->n + 1 the results are undefined.  bt_kychildp is a macro.
  29.  
  30. SEE ALSO
  31.      bt_kykeyp.
  32.  
  33. ------------------------------------------------------------------------------*/
  34. /* bt_kychildp is defined in btree_.h. */
  35.  
  36. /*man---------------------------------------------------------------------------
  37. NAME
  38.      bt_kykeyp - btree node key
  39.  
  40. SYNOPSIS
  41.      #include "btree_.h"
  42.  
  43.      void *bt_kykeyp(btnp, kn)
  44.      btnode_t *btnp;
  45.      int kn;
  46.  
  47. DESCRIPTION
  48.      bt_kykeyp returns a pointer to the knth key in node btnp.  If
  49.      btnp is not a valid btree node or if kn < 1 or kn > btnp->n + 1
  50.      the results are undefined.  bt_kychildp is a macro.
  51.  
  52. SEE ALSO
  53.      bt_kychildp.
  54.  
  55. ------------------------------------------------------------------------------*/
  56. /* bt_kykeyp is defined in btree_.h. */
  57.  
  58. /*man---------------------------------------------------------------------------
  59. NAME
  60.      bt_kykfp - btree node key field
  61.  
  62. SYNOPSIS
  63.      #include "btree_.h"
  64.  
  65.      void *bt_kykfp(btp, btnp, kn, fn)
  66.      btree_t *btp;
  67.      btnode_t *btnp;
  68.      int kn;
  69.      int fn;
  70.  
  71. DESCRIPTION
  72.      bt_kykfp returns a pointer to the fnth field of the knth key in
  73.      node btnp.  If btnp is not a valid btree node or if kn < 1 or
  74.      kn > btnp->n + 1 the results are undefined.  bt_kychildp is a
  75.      macro.
  76.  
  77. SEE ALSO
  78.      bt_kychildp.
  79.  
  80. ------------------------------------------------------------------------------*/
  81. /* bt_kykfp is defined in btree_.h. */
  82.  
  83. /*man---------------------------------------------------------------------------
  84. NAME
  85.      bt_kymvleft - move keys left
  86.  
  87. SYNOPSIS
  88.      #include "btree_.h"
  89.  
  90.      int bt_kymvleft(btp, lbtnp, rbtnp, nm)
  91.      btree_t *btp;
  92.      btnode_t *lbtnp;
  93.      btnode_t *rbtnp;
  94.      int nm;
  95.  
  96. DESCRIPTION
  97.      Function moves the leftmost nm tuples and child 0 (keys 1..nm and
  98.      children 0..nm) from node rbtnp to lbtnp.  They are appended
  99.      after the last key in lbtnp, its rightmost child being
  100.      overwritten.  The key count in each node is corrected for the
  101.      shift.  No other changes are made.
  102.  
  103.      bt_kymvleft will fail if one or more of the following is true: 
  104.  
  105.      [EINVAL]       btp is not a valid btree pointer.
  106.      [EINVAL]       lbtnp or rbtnp is NULL. 
  107.      [EINVAL]       lbtnp and rbtnp point to the same node.
  108.      [EINVAL]       rbtnp has less than nm keys.
  109.      [EINVAL]       lbtnp does not have room for nm keys.
  110.  
  111. SEE ALSO
  112.      bt_kymvright, bt_kyshift.
  113.  
  114. DIAGNOSTICS
  115.      Upon successful completion, a value of 0 is returned.  Otherwise,
  116.      a value of -1 is returned, and errno set to indicate the error.
  117.  
  118. ------------------------------------------------------------------------------*/
  119. int bt_kymvleft(btp, lbtnp, rbtnp, nm)
  120. btree_t *btp;
  121. btnode_t *lbtnp;
  122. btnode_t *rbtnp;
  123. int nm;
  124. {
  125.     int    ks = 0;        /* first key to copy */
  126.     int    ke = 0;        /* last key to copy */
  127.     int    kt = 0;        /* target key */
  128.     void *    ps = NULL;    /* pointer to copy source */
  129.     void *    pe = NULL;    /* pointer to copy source end */
  130.     void *    pt = NULL;    /* pointer to copy target */
  131. #ifdef DEBUG
  132.     /* validate arguments */
  133.     if (!bt_valid(btp) || lbtnp == NULL || rbtnp == NULL || lbtnp == rbtnp) {
  134.         BTEPRINT;
  135.         errno = EINVAL;
  136.         return -1;
  137.     }
  138.     if (nm > rbtnp->n || nm + lbtnp->n > bt_ndmax(btp) + 1) {
  139.         BTEPRINT;
  140.         errno = EINVAL;
  141.         return -1;
  142.     }
  143. #endif
  144.     /* move bttpls */
  145.     ks = 1;
  146.     ke = nm;
  147.     kt = lbtnp->n + 1;
  148.     ps = bt_kykeyp(btp, rbtnp, ks);
  149.     pe = bt_kykeyp(btp, rbtnp, ke + 1);
  150.     pt = bt_kykeyp(btp, lbtnp, kt);
  151.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  152.     ps = bt_kychildp(rbtnp, ks - 1);
  153.     pe = bt_kychildp(rbtnp, ke + 1);
  154.     pt = bt_kychildp(lbtnp, kt - 1);
  155.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  156.  
  157.     /* adjust key count of left node */
  158.     lbtnp->n += nm;
  159.  
  160.     /* delete keys from rbtnp */
  161.     ks = nm + 1;
  162.     ke = rbtnp->n;
  163.     kt = 1;
  164.     ps = bt_kykeyp(btp, rbtnp, ks);
  165.     pe = bt_kykeyp(btp, rbtnp, ke + 1);
  166.     pt = bt_kykeyp(btp, rbtnp, kt);
  167.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  168.     ps = bt_kychildp(rbtnp, ks - 1);
  169.     pe = bt_kychildp(rbtnp, ke + 1);
  170.     pt = bt_kychildp(rbtnp, kt - 1);
  171.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  172.  
  173.     /* adjust key count of right node */
  174.     rbtnp->n -= nm;
  175.     if (rbtnp->n < btp->bthdr.m) {
  176.         ps = bt_kykeyp(btp, rbtnp, rbtnp->n + 1);
  177.         pe = bt_kykeyp(btp, rbtnp, btp->bthdr.m + 1);
  178.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  179.         ps = bt_kychildp(rbtnp, rbtnp->n + 1);
  180.         pe = bt_kychildp(rbtnp, btp->bthdr.m + 1);
  181.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  182.     }
  183.  
  184.     errno = 0;
  185.     return 0;
  186. }
  187.  
  188. /*man---------------------------------------------------------------------------
  189. NAME
  190.      bt_kymvright - move keys right
  191.  
  192. SYNOPSIS
  193.      #include "btree_.h"
  194.  
  195.      int bt_kymvright(btp, lbtnp, rbtnp, nm)
  196.      btree_t *btp;
  197.      btnode_t *lbtnp;
  198.      btnode_t *rbtnp;
  199.      int nm;
  200.  
  201. DESCRIPTION
  202.      Function moves the rightmost nm bttpls and the child preceding
  203.      them (keys (n + 1 - nm)..n and children (n - nm)..n) from node
  204.      lbtnp to rbtnp.  They are inserted before the first key in rbtnp,
  205.      its leftmost child being overwritten.  The key count in each node
  206.      is corrected for the shift.  No other changes are made.
  207.  
  208.      bt_kymvright will fail if one or more of the following is true: 
  209.  
  210.      [EINVAL]       btp is not a valid btree pointer.
  211.      [EINVAL]       lbtnp or rbtnp is NULL. 
  212.      [EINVAL]       lbtnp and rbtnp are same node.
  213.      [EINVAL]       rbtnp does not have nm keys.
  214.      [EINVAL]       lbtnp does not have room for nm keys.
  215.  
  216. SEE ALSO
  217.      bt_kymvleft, bt_kyshift.
  218.  
  219. DIAGNOSTICS
  220.      Upon successful completion, a value of 0 is returned.  Otherwise,
  221.      a value of -1 is returned, and errno set to indicate the error.
  222.  
  223. ------------------------------------------------------------------------------*/
  224. int bt_kymvright(btp, lbtnp, rbtnp, nm)
  225. btree_t *btp;
  226. btnode_t *lbtnp;
  227. btnode_t *rbtnp;
  228. int nm;
  229. {
  230.     int    ks = 0;        /* first key to copy */
  231.     int    ke = 0;        /* last key to copy */
  232.     int    kt = 0;        /* target key */
  233.     void *    ps = NULL;    /* pointer to copy source */
  234.     void *    pe = NULL;    /* pointer to copy source end */
  235.     void *    pt = NULL;    /* pointer to copy target */
  236. #ifdef DEBUG
  237.     /* validate arguments */
  238.     if (!bt_valid(btp) || lbtnp == NULL || rbtnp == NULL || lbtnp == rbtnp) {
  239.         BTEPRINT;
  240.         errno = EINVAL;
  241.         return -1;
  242.     }
  243.     if (nm > lbtnp->n || nm + rbtnp->n > bt_ndmax(btp) + 1) {
  244.         BTEPRINT;
  245.         errno = EINVAL;
  246.         return -1;
  247.     }
  248. #endif
  249.     /* make room in right node */
  250.     ks = 1;
  251.     ke = rbtnp->n;
  252.     kt = nm + 1;
  253.     ps = bt_kykeyp(btp, rbtnp, ks);
  254.     pe = bt_kykeyp(btp, rbtnp, ke + 1);
  255.     pt = bt_kykeyp(btp, rbtnp, kt);
  256.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  257.     ps = bt_kychildp(rbtnp, ks - 1);
  258.     pe = bt_kychildp(rbtnp, ke + 1);
  259.     pt = bt_kychildp(rbtnp, kt - 1);
  260.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  261.  
  262.     /* adjust key count of right node */
  263.     rbtnp->n += nm;
  264.  
  265.     /* move bttpls */
  266.     ks = lbtnp->n - nm + 1;
  267.     ke = lbtnp->n;
  268.     kt = 1;
  269.     ps = bt_kykeyp(btp, lbtnp, ks);
  270.     pe = bt_kykeyp(btp, lbtnp, ke + 1);
  271.     pt = bt_kykeyp(btp, rbtnp, kt);
  272.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  273.     memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  274.     ps = bt_kychildp(lbtnp, ks - 1);
  275.     pe = bt_kychildp(lbtnp, ke + 1);
  276.     pt = bt_kychildp(rbtnp, kt - 1);
  277.     memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
  278.     ps = bt_kychildp(lbtnp, ks);
  279.     memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  280.  
  281.     /* adjust key count of left node */
  282.     lbtnp->n -= nm;
  283.  
  284.     errno = 0;
  285.     return 0;
  286. }
  287.  
  288. /*man---------------------------------------------------------------------------
  289. NAME
  290.      bt_kyread - read key
  291.  
  292. SYNOPSIS
  293.      #include "btree_.h"
  294.  
  295.      int bt_kyread(btp, btnp, kn, bttplp)
  296.      btree_t *btp;
  297.      btnode_t *btnp;
  298.      int kn;
  299.      bttpl_t *bttplp;
  300.  
  301. DESCRIPTION
  302.      Function reads the (key, child) bttpl in slot kn of node btnp.
  303.      The results are returned in bttplp.  If kn is zero, then the key
  304.      field of bttplp is cleared and child 0 is written in the child
  305.      field.
  306.  
  307.      bt_kyread will fail if one or more of the following is true:
  308.  
  309.      [EINVAL]       btp, btnp, or bttplp is NULL. 
  310.      [EINVAL]       btnp contains fewer than kn keys.
  311.      [EINVAL]       kn < 0 or kn > btnp->n.
  312.  
  313. SEE ALSO
  314.      bt_kywrite.
  315.  
  316. DIAGNOSTICS
  317.      Upon successful completion, a value of 0 is returned.  Otherwise,
  318.      a value of -1 is returned, and errno set to indicate the error.
  319.  
  320. ------------------------------------------------------------------------------*/
  321. int bt_kyread(btp, btnp, kn, bttplp)
  322. btree_t *btp;
  323. const btnode_t *btnp;
  324. int kn;
  325. bttpl_t *bttplp;
  326. {
  327. #ifdef DEBUG
  328.     /* validate arguments */
  329.     if (!bt_valid(btp) || btnp == NULL || bttplp == NULL) {
  330.         BTEPRINT;
  331.         errno = EINVAL;
  332.         return -1;
  333.     }
  334.     if (kn < 0 || kn > btnp->n) {
  335.         BTEPRINT;
  336.         errno = EINVAL;
  337.         return -1;
  338.     }
  339. #endif
  340.     if (kn == 0) {
  341.         memset(bttplp->keyp, 0, sizeof(bttplp->keyp));
  342.     } else {
  343.         memcpy(bttplp->keyp, bt_kykeyp(btp, btnp, kn), btp->bthdr.keysize);
  344.     }
  345.     bttplp->child = *bt_kychildp(btnp, kn);
  346.  
  347.     errno = 0;
  348.     return 0;
  349. }
  350.  
  351. /*man---------------------------------------------------------------------------
  352. NAME
  353.      bt_kyshift - shift keys
  354.  
  355. SYNOPSIS
  356.      #include "btree_.h"
  357.  
  358.      int bt_kyshift(btp, btnp, kn, ns)
  359.      btree_t *btp;
  360.      btnode_t *btnp;
  361.      int kn;
  362.      int ns;
  363.  
  364. DESCRIPTION
  365.      Function shifts bttpls kn and above in node btnp by ns slots.  If
  366.      ns > 0, the keys are shifted up.  If ns < 0, they are shifted
  367.      down.  The key count in is corrected for the shift.  No other
  368.      changes are made.
  369.  
  370.      bt_kymvleft will fail if one or more of the following is true: 
  371.  
  372.      [EINVAL]       btp is not a valid btree pointer.
  373.      [EINVAL]       btnp is NULL. 
  374.      [EINVAL]       kn < 1 or kn > btnp->n + 1.
  375.  
  376. SEE ALSO
  377.      bt_kymvleft, bt_kymvright.
  378.  
  379. DIAGNOSTICS
  380.      Upon successful completion, a value of 0 is returned.  Otherwise,
  381.      a value of -1 is returned, and errno set to indicate the error.
  382.  
  383. ------------------------------------------------------------------------------*/
  384. int bt_kyshift(btp, btnp, kn, ns)
  385. btree_t *btp;
  386. btnode_t *btnp;
  387. int kn;
  388. int ns;
  389. {
  390.     int    ks = 0;        /* first key to copy */
  391.     int    ke = 0;        /* last key to copy */
  392.     int    kt = 0;        /* target key */
  393.     void *    ps = NULL;    /* pointer to copy source */
  394.     void *    pe = NULL;    /* pointer to copy source end */
  395.     void *    pt = NULL;    /* pointer to copy target */
  396. #ifdef DEBUG
  397.     /* validate arguments */
  398.     if (!bt_valid(btp) || btnp == NULL) {
  399.         BTEPRINT;
  400.         errno = EINVAL;
  401.         return -1;
  402.     }
  403.     if (kn < 1 || kn > btnp->n + 1) {
  404.         BTEPRINT;
  405.         errno = EINVAL;
  406.         return -1;
  407.     }
  408. #endif
  409.     if (((int)btnp->n + ns) > (int)btp->bthdr.m) {/* keys shifted out top */
  410.         BTEPRINT;
  411.         errno = BTEPANIC;
  412.         return -1;
  413.     }
  414.     if (-ns >= (int)kn) {            /* keys shifted out bottom */
  415.         BTEPRINT;
  416.         errno = BTEPANIC;
  417.         return -1;
  418.     }
  419.  
  420.     /* shift keys */
  421.     ks = kn;
  422.     ke = btnp->n;
  423.     kt = kn + ns;
  424.     ps = bt_kykeyp(btp, btnp, ks);
  425.     pe = bt_kykeyp(btp, btnp, ke + 1);
  426.     pt = bt_kykeyp(btp, btnp, kt);
  427.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  428.     ps = bt_kychildp(btnp, ks);
  429.     pe = bt_kychildp(btnp, ke + 1);
  430.     pt = bt_kychildp(btnp, kt);
  431.     memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
  432.  
  433.     /* adjust number of keys */
  434.     btnp->n = (int)btnp->n + ns;
  435.  
  436.     /* clear memory above last key */
  437.     if (ns < 0) {
  438.         ps = bt_kykeyp(btp, btnp, btnp->n + 1);
  439.         pe = bt_kykeyp(btp, btnp, btp->bthdr.m + 1);
  440.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  441.         ps = bt_kychildp(btnp, btnp->n + 1);
  442.         pe = bt_kychildp(btnp, btp->bthdr.m + 1);
  443.         memset(ps, 0, (size_t)((char *)pe - (char *)ps));
  444.     }
  445.  
  446.     errno = 0;
  447.     return 0;
  448. }
  449.  
  450. /*man---------------------------------------------------------------------------
  451. NAME
  452.      bt_kywrite - write key
  453.  
  454. SYNOPSIS
  455.      #include "btree_.h"
  456.  
  457.      int bt_kywrite(btp, btnp, kn, bttplp)
  458.      btree_t *btp;
  459.      btnode_t *btnp;
  460.      int kn;
  461.      const bttpl_t *bttplp;
  462.  
  463. DESCRIPTION
  464.      Function writes the (key, child) bttpl contained in bttplp in
  465.      slot kn of node btnp.  If kn is zero, then the contents of the
  466.      key field of bttplp are ignored and the contents of the child
  467.      field are written to child 0 of btnp.  If bttplp is NULL, the
  468.      slot is cleared.
  469.  
  470.      bt_kywrite will fail if one or more of the following is true:
  471.  
  472.      [EINVAL]       btp is not a valid btree pointer.
  473.      [EIVNAL]       btnp is NULL. 
  474.      [EINVAL]       btnp contains fewer than kn keys.
  475.  
  476. SEE ALSO
  477.      bt_kywrite.
  478.  
  479. DIAGNOSTICS
  480.      Upon successful completion, a value of 0 is returned.  Otherwise,
  481.      a value of -1 is returned, and errno set to indicate the error.
  482.  
  483. ------------------------------------------------------------------------------*/
  484. int bt_kywrite(btp, btnp, kn, bttplp)
  485. btree_t *btp;
  486. btnode_t *btnp;
  487. int kn;
  488. const bttpl_t *bttplp;
  489. {
  490. #ifdef DEBUG
  491.     /* validate arguments */
  492.     if (!bt_valid(btp) || btnp == NULL) {
  493.         BTEPRINT;
  494.         errno = EINVAL;
  495.         return -1;
  496.     }
  497.     if (kn < 0 || kn > btnp->n) {
  498.         BTEPRINT;
  499.         errno = EINVAL;
  500.         return -1;
  501.     }
  502. #endif
  503.     if (bttplp == NULL) {
  504.         if (kn != 0) {
  505.             memset(bt_kykeyp(btp, btnp, kn), 0, btp->bthdr.keysize);
  506.         }
  507.         *bt_kychildp(btnp, kn) = NIL;
  508.     } else {
  509.         if (kn != 0) {
  510.             memcpy(bt_kykeyp(btp, btnp, kn), bttplp->keyp, btp->bthdr.keysize);
  511.         }
  512.         *bt_kychildp(btnp, kn) = bttplp->child;
  513.     }
  514.  
  515.     errno = 0;
  516.     return 0;
  517. }
  518.